from typing import List

from sortedcontainers import SortedList


# 测试用例 51/67


class Node:
    def __init__(self, idx, num, parent=None):
        self.idx = idx
        self.num = num
        self.children = []


class Solution:
    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:
        # ---------- 构造树结构 ----------
        n = len(parents)
        nodes = {i: Node(i, nums[i]) for i in range(n)}
        for i, parent in enumerate(parents):
            if parent != -1:
                nodes[parent].children.append(nodes[i])
            else:
                root = nodes[i]

        # ---------- 计算最终结果 ----------
        ans = [0] * n

        def dfs(node):
            if not node.children:
                lst = SortedList([node.num])
            else:
                first_child = node.children[0]
                lst = dfs(first_child)
                for i in range(1, len(node.children)):
                    lst.update(dfs(node.children[i]))
                lst.add(node.num)

            # 二分查找寻找最小缺失
            left, right = 0, len(lst)
            while left < right:
                mid = (left + right) // 2
                if lst[mid] == mid + 1:
                    left = mid + 1
                else:
                    right = mid

            # print(node.idx, ":", lst, "->", left, "->", left + 1)
            ans[node.idx] = left + 1
            return lst

        dfs(root)

        return ans


if __name__ == "__main__":
    # [5,1,1,1]
    print(Solution().smallestMissingValueSubtree(parents=[-1, 0, 0, 2],
                                                 nums=[1, 2, 3, 4]))

    # [7,1,1,4,2,1]
    print(Solution().smallestMissingValueSubtree(parents=[-1, 0, 1, 0, 3, 3],
                                                 nums=[5, 4, 6, 2, 1, 3]))

    # [1,1,1,1,1,1,1]
    print(Solution().smallestMissingValueSubtree(parents=[-1, 2, 3, 0, 2, 4, 1],
                                                 nums=[2, 3, 4, 5, 6, 7, 8]))
